﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// LCA : 두 노드 사이의 가장 가까운 동일 부모 찾기
    /// RMQ 수정필요...
    /// </summary>
    class LCAByRMQ
    {
        private List<Edge>[] G;
        private int root;
        int[] vs; //DFS에서의 방문순서
        int[] depth; //루트로부터의 깊이
        int[] id; //각 정점을 e에 처음 등록하는 인덱스
        int V;

        SegmentTree s;

        public LCAByRMQ(List<Edge>[] G, int maxSize, int root)
        {
            this.root = root;
            this.V = maxSize;
            this.G = G;
            vs = new int[maxSize * 2 - 1];
            depth = new int[maxSize * 2 - 1];
            id = new int[maxSize + 1];
            Init();
        }

        private void Dfs(int v, int p, int d, ref int k)
        {
            id[v] = k;
            vs[k] = v;
            depth[k++] = d;
            for (int i = 0; i < G[v].Count; i++)
            {
                if (G[v][i].To != p)
                {
                    Dfs(G[v][i].To, v, d + 1, ref k);
                    vs[k] = v;
                    depth[k++] = d;
                }
            }
        }
        private void Init()
        {
            int k = 0;
            Dfs(root, -1, 0, ref k);
            s = new SegmentTree(depth);
        }
        public int LCA(int u, int v)
        {
            return vs[s.Query(Math.Min(id[u], id[v]), Math.Max(id[u], id[v]) + 1)];
        }
    }
}
